/*******************************************

  TRABALHO DE CONCORRENTES - PROJETO 2

  Hospital ICMCTown

********************************************/

/*********************
Bibliotecas
*********************/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <assert.h>
#include "mpi.h"

/*********************
Definições
*********************/
#define MASTER      0          /* taskid of first task */
#define FROM_MASTER 1          /* setting a message type */
#define FROM_WORKER 2          /* setting a message type */

#define INFINITE    1000000000
#define THREAD      16

/*********************
Funções gerais
*********************/

//  int readNumJuncoes()
//  le o numero de Juncoes
  int readNumJuncoes()
  {
    int numJuncoes;

    scanf("%d", &numJuncoes);
    if( !((numJuncoes >= 2) && (numJuncoes <= 1000)) )
    {
      printf("-----------\nNumero de Juncoes nao esta no intervalo especificado.\n-----------\n\n");
      abort();
    }

    return numJuncoes;
  }

//  int readNumLinhas(int numJuncoes)
//  Le o numero de Linhas
  int readNumLinhas(int numJuncoes)
  {
    int numLinhas;

    scanf("%d", &numLinhas);
    if( !((numLinhas >= (numJuncoes-1)) && ( numLinhas <= ((numJuncoes*(numJuncoes-1))/2))) )
    {
      printf("-----------\nNumero de Linhas nao esta no intervalo especificado.\n-----------\n\n");
      abort();
    }

    return numLinhas;
  }



//  void defineJuncoes(int *a, int *b, int i, int numJuncoes)
//  coloca as informacoes das juncoes nos vetores
  void defineJuncoes(int *a, int *b, int i, int numJuncoes)
  {
    scanf("%d", &a[i]);
    if( !(a[i] >= 1 && a[i] <= numJuncoes) ) printf("-----------\nJuncao nao esta existe.\n-----------\n\n"), abort();
    
    scanf("%d", &b[i]);
    if( !(b[i] >= 1 && b[i] <= numJuncoes) ) printf("-----------\nJuncao nao esta existe.\n-----------\n\n"), abort();
    if( a[i] == b[i] ) printf("-----------\nJuncoes iguais.\n-----------\n\n"), abort();
  }

//  void distanciaJuncoes(int *w, int i)
//  coloca as informacoes das juncoes nos vetores
  void distanciaJuncoes(int *w, int i)
  {
    scanf("%d", &w[i]);
    if( !(w[i] >= 1 && w[i] <= 100000) ) printf("-----------\nTamanho do caminho nao esta no intervalo especificado.\n-----------\n\n"), abort();
  }

// void montarGrafo(int *a, int *b, int *w, int numJuncoes, int numLinhas, int **grafo)
// Monta o grafo das distancias, sendo linha referente a juncao inicial, coluna a final e o valor a distancia
  void montarGrafo(int *a, int *b, int *w, int numJuncoes, int numLinhas, int **grafo)
  {
    int i, j;

    for(i=0;i<numLinhas;i++)
    {
      grafo[a[i]-1][b[i]-1] = w[i];
      grafo[b[i]-1][a[i]-1] = w[i];
    }
  }


  void converteGrafoVet(int **grafo, int *grafovet, int numJuncoes)
  {
    int i, j, d=0;

    for(i=0;i<numJuncoes;i++)
    {
      for(j=0;j<numJuncoes;j++)
      {
        grafovet[d++] = grafo[i][j];
      }
    }
  }

  void converteGrafo(int **grafo, int *grafovet, int numJuncoes)
  {
    int i, j, d=0;

    for(i=0;i<numJuncoes;i++)
    {
      for(j=0;j<numJuncoes;j++)
      {
        grafo[i][j] = grafovet[d++];
      }
    }
  }

// int minDistance(int dist[], int numJuncoes, bool sptSet[])
// Acha a distancia vertice com a menor distancia
  int minDistance(int *dist, int numJuncoes, bool *sptSet)
  {
   int min = INT_MAX, min_index;
   int v;
   for (v = 0; v < numJuncoes; v++)
     if (sptSet[v] == false && dist[v] <= min)
       min = dist[v], min_index = v;

     return min_index;
   }

// int maximo(int *dist int numJuncoes)
// Acha a maior distancia do conjunto do vetor de distancias
  int maximo(int *dist, int numJuncoes)
  {
   int i, aux=0;
   for (i = 0; i < numJuncoes; i++)
    if(dist[i] > aux) aux = dist[i];
  return aux;
  }

// int dijkstra(int **graph, int numJuncoes, int src)
// Implementa o algoritmo de Dijkstra
  int dijkstra(int **graph, int numJuncoes, int src)
  {
     int i, count,v;
     int dist[numJuncoes];     // O vetor de distrancias.
                               // dist[i] terá a menor distância da raiz até i

     bool sptSet[numJuncoes];  // sptSet[i] irá definir como verdadeiro se o vértice i estiver incluso na
                               // arvore de menor caminho ou menor distância da raiz até o vértice estiver
                               // finalizada

     // Inicializa todas as distâncias em infinito e os caminhos como falsos(não acessados)
     for (i = 0; i < numJuncoes; i++)
      dist[i] = INT_MAX, sptSet[i] = false;

     // Distância do vértice raiz a ele mesmo é zero (Sempreee!)
     dist[src] = 0;

     // Encontra o menor caminho para todos os vértices
    for (count = 0; count < numJuncoes-1; count++)
    {
      // Pega a menor distância do conjunto de vértices ainda não processado 
      int u = minDistance(dist, numJuncoes, sptSet);

      // Marca o vértice como processado
      sptSet[u] = true;

      // Atualiza o valor da distância dos vértices adjacentes ao vértice pego
      for (v = 0; v < numJuncoes; v++)

       // Atualiza dist[v] somente se não estiver em sptSet, onde houver uma conexão de
       // u até v, e o peso total do caminho da raiz até v através de u for menor do que
       // o atual valor da distância de dist[v]
       if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
         && dist[u]+graph[u][v] < dist[v])
          dist[v] = dist[u] + graph[u][v];
    }

    // retorna o valor maximo de todas as distancias encontradas
    return maximo(dist,numJuncoes);
  }



/******************
Função Principal
*******************/
  int main(int argc, char *argv[])
  {
    int numLinhas, numJuncoes;
    int *a,*b,*w;     // a[] e b[]  numero das juncoes
                      // w[]        distancia das juncoes
    int min[2000];
    int aux=INFINITE;

    int i;            // contador
    int j;

    int **grafo;
    int *grafovet;

    //MPI Code
    int taskid,         /* task ID - also used as seed number */
    numtasks,
    chunksize,
    sobra,
    chunksizesobra,
    offset,
    dest,
    source;

    // Inicialização do MPI
    MPI_Status status;
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
    MPI_Comm_rank(MPI_COMM_WORLD,&taskid);

    
    /************************************************/
    /**************** Processo Pai ******************/
    /************************************************/
    if (taskid == MASTER) {

      // Entrada de Dados
      numJuncoes = readNumJuncoes();
      numLinhas = readNumLinhas(numJuncoes);

      // Divide a quantidade de tarefas/cluster sobre o tamanho de Juncoes(execucao do algoritmo de Dijkstra)
      chunksize = (numJuncoes / (numtasks-1));
      sobra = (numJuncoes % (numtasks-1));
      chunksizesobra= chunksize+sobra;

      // Alocação de variaveis
      a = (int *) calloc(numLinhas,sizeof(int));
      b = (int *) calloc(numLinhas,sizeof(int));
      w = (int *) calloc(numLinhas,sizeof(int));
      //min = (int *) calloc(numJuncoes,sizeof(int));

      // Entrada de Dados
      for(i=0;i<numLinhas; i++)
      {
        defineJuncoes(a,b,i,numJuncoes);
        distanciaJuncoes(w,i);
      }

      grafo = (int **) calloc(numJuncoes,sizeof(int *));
      for(i=0;i<numJuncoes+1;i++) grafo[i] = (int *) calloc(numJuncoes,sizeof(int));
      grafovet = (int *) calloc(numJuncoes*numJuncoes,sizeof(int));
      
      montarGrafo(a,b,w,numJuncoes,numLinhas,grafo);
      converteGrafoVet(grafo, grafovet, numJuncoes);

      //for(i=0;i<numJuncoes;i++)
      //  min[i] = i;

      // Aqui efetivamente iniciamos a execução do algoritmo
      // Serão enviadas para os processos filhos as informações necessárias
      // Para calcular o algoritmo      
      offset = 0;
      for (dest=1; dest<numtasks; dest++)
      {
        MPI_Send(&offset, 1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
        if(dest==numtasks-1)
          MPI_Send(&chunksizesobra, 1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
        else
          MPI_Send(&chunksize, 1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
        MPI_Send(&numJuncoes, 1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
      //  MPI_Send(min, numJuncoes, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
        MPI_Send(grafovet, numJuncoes*numJuncoes, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
        offset += chunksize;
      }
      
      // Espera receber as informações dos filhos
      for (i=1; i<numtasks; i++)
      {
        source = i;
        MPI_Recv(&offset, 1, MPI_INT, source, FROM_WORKER, MPI_COMM_WORLD, &status);
        MPI_Recv(&numJuncoes, 1, MPI_INT, source, FROM_WORKER, MPI_COMM_WORLD, &status);
        MPI_Recv(&min[offset], numJuncoes, MPI_INT, source, FROM_WORKER, MPI_COMM_WORLD, &status);
      }

      //for(i=0;i<numJuncoes;i++)
      //  printf("min: %d\n", min[i]);


      // Calcula o mínimo
      #pragma omp parallel num_threads(THREAD) 
      {
        #pragma omp for
        for(i=0;i<numJuncoes;i++)
          if(min[i] < aux) aux = min[i];
      }

      printf("%d\n", aux);

    }

    /************************************************/
    /************* Processos Filhos *****************/
    /************************************************/
    if (taskid > MASTER)
    {
      //Recebe as informações
      source = MASTER;
      MPI_Recv(&offset, 1, MPI_INT, source, FROM_MASTER, MPI_COMM_WORLD, &status);
      MPI_Recv(&chunksize, 1, MPI_INT, source, FROM_MASTER, MPI_COMM_WORLD, &status);
      MPI_Recv(&numJuncoes, 1, MPI_INT, source, FROM_MASTER, MPI_COMM_WORLD, &status);
      // min = (int *) calloc(numJuncoes,sizeof(int));
      // MPI_Recv(min, numJuncoes, MPI_INT, source, FROM_MASTER, MPI_COMM_WORLD, &status);

      grafo = (int **) calloc(numJuncoes,sizeof(int *));
      for(i=0;i<numJuncoes+1;i++) grafo[i] = (int *) calloc(numJuncoes,sizeof(int));
      grafovet = (int *) calloc(numJuncoes*numJuncoes,sizeof(int));
      MPI_Recv(grafovet, numJuncoes*numJuncoes, MPI_INT, source, FROM_MASTER, MPI_COMM_WORLD, &status);
      converteGrafo(grafo, grafovet, numJuncoes);

      #pragma omp parallel num_threads(THREAD) 
      {
        #pragma omp for
        // Calcula o algoritmo
        for(i=offset; i < offset + chunksize; i++)
        {
          min[i] = dijkstra(grafo, numJuncoes, i);
        //  printf("%d: %d\n", taskid, min[i] );
        }
      }

      // Devolve as informações necessárias
      dest = MASTER;
      MPI_Send(&offset, 1, MPI_INT, dest, FROM_WORKER, MPI_COMM_WORLD);
      MPI_Send(&numJuncoes, 1, MPI_INT, dest, FROM_WORKER, MPI_COMM_WORLD);
      MPI_Send(&min[offset], numJuncoes, MPI_INT, dest, FROM_WORKER, MPI_COMM_WORLD);
    }

    // Finaliza o MPI
    MPI_Finalize();   

    // Libera informações
    //free(a);
    //free(b);
    //free(w);
    //free(min);
    //for(i=0;i<numJuncoes+1;i++) free(grafo[i]);
    //free(grafo);
  }
